package _41_和为S的连续正数序列;

import java.util.ArrayList;

/**
 * 题目描述
 * 小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上就写出了正确答案是100。
 * 但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为100(至少包括两个数)。
 * 没多久,他就得到另一组连续正数和为100的序列:18,19,20,21,22。现在把问题交给你,你能不能也很快的找出所有和为S的连续正数序列? Good Luck!
 */

/**
 * 我的思路：
 *         大小指针，和小于sum时，大指针+1，大于时，小指针+1，指针不超过 sum的一半
 */
public class Solution {
    public ArrayList<ArrayList<Integer>> FindContinuousSequence(int sum) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        if(sum<=2) return res;

        int start =1,end=2;
        while(end<=(sum+1)/2){
           int tmp= sumNums(start,end);
           if(tmp==sum){
               ArrayList<Integer> ls = new ArrayList<>();
               for(int i=start;i<=end;i++){
                   ls.add(i);
               }
               res.add(ls);
               end++;
           }
           else if(tmp<sum){
               end++;
           }else {
               start++;
           }
        }
        System.out.println(res);
        return res;

    }

    int sumNums(int start,int end){
        return (start+end)*(end-start+1)/2;

    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        solution.FindContinuousSequence(3);

    }
}
